package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/2 14:25
 * @description :
 */
public class 网络延迟时间 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.networkDelayTime(new int[][]{{1, 2, 1}, {2, 3, 2}, {1, 3, 2}}, 3, 1));
    }

    //时间 -> 最小堆
    class Solution {
        public int networkDelayTime(int[][] times, int n, int k) {
            //初始化数据
            int curTime = 0;
            ArrayList<int[]> list = new ArrayList<>();
            for (int[] time : times) {
                list.add(time);
            }
            list.sort((o1, o2) -> o1[0] - o2[0]);
            Map<Integer, PriorityQueue<int[]>> map = new HashMap<>();
            PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
            HashSet<Integer> set = new HashSet<>();//存放已经送达的节点
            set.add(k);
            Iterator<int[]> iterator = list.iterator();
            while (iterator.hasNext()) {
                int[] num = iterator.next();
                if (num[0] > k) break;
                if (num[0] == k) {
                    queue.add(new int[]{num[1], num[2]});
                    iterator.remove();
                }
            }
            map.put(curTime, queue);
            while (true) {
                PriorityQueue<int[]> priorityQueue = map.get(curTime);
                if (priorityQueue == null || priorityQueue.size() == 0) break;
                curTime = priorityQueue.peek()[1];
                ArrayList<Integer> list1 = new ArrayList<>();
                while (!priorityQueue.isEmpty() && priorityQueue.peek()[1] <= curTime) {
                    int[] cur = priorityQueue.poll();
                    list1.add(cur[0]);
                    set.add(cur[0]);
                }
                if (set.size() == n) return curTime;
                PriorityQueue<int[]> nextTimeQueue = new PriorityQueue<>(priorityQueue);
                for (Integer integer : list1) {
                    Iterator<int[]> iterator1 = list.iterator();
                    while (iterator1.hasNext()) {
                        int[] num = iterator1.next();
                        if (num[0] > integer) break;
                        if (num[0] == integer) {
                            nextTimeQueue.add(new int[]{num[1], num[2] + curTime});
                            iterator1.remove();

                        }
                    }
                }
                map.put(curTime, nextTimeQueue);
            }
            PriorityQueue<int[]> ints = map.get(curTime);
            while (!ints.isEmpty()) {
                curTime = ints.poll()[1];
            }
            return set.size() == n ? curTime : -1;
        }
    }
}
